//
//  ChainList.c
//  DataStruct
//
//  Created by vase on 2022/2/25.
//  线性表的链式存储

#include "ChainList.h"

/** 初始化头指针并返回*/
ListNode* initLinkedList(void) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = INT_MAX;
    node->next = NULL;
    return node;
}

/** 不停地在头节点后面加元素，之前的元素挂在新元素的后面*/
void addInHead(ListNode *head, int value) {
    ListNode *new = (ListNode *)malloc(sizeof(ListNode)); //创建新节点
    new->data = value;
    new->next = head->next;
    head->next = new; //挂载到头节点后面
}

/** 把新元素挂到最后*/
void addInTail(ListNode *head, int value) {
    ListNode *new = (ListNode *)malloc(sizeof(ListNode)); //创建新节点
    new->data = value;
    new->next = NULL;
    //循环遍历到最后一个元素
    while (head->next != NULL) {
        head = head->next;
    }
    head->next = new; //挂载到最后一个元素后面
}

/** 递归删除*/
void recursionDelX(ListNode *head, ListNode *pre, int value) {
    if (head == NULL) {  //递归条件
        return ;
    }
    //递归下一节点
    recursionDelX(head->next, head, value);
    if (head->data == value) { //查找到指定元素则删除之
        pre->next = head->next;
        free(head); // 释放空间
    }
}

/** 遍历寻找最小值，并记录位置，伺机删除*/
void removeMinList(ListNode *head) {
//    int min = INT_MAX;
//    ListNode *back = head, *pre = head;
//    head = head->next;
//    while (head != NULL) {
//        if (head->data < min) {
//            min = head->data;
//        }
//    }
//    while (back != NULL) {
//        if (back->data == min) {
//            
//        }
//    }
}

/** 递归处理*/
void reverseOnSite(ListNode *now, ListNode *head) {
    if (now == NULL) {  //递归终止条件
        head->next = NULL;
        return ;
    }
    reverseOnSite(now->next, head);  //递归到下一个节点
    //挂载节点到尾巴上
    while (head->next != NULL) {
        head = head->next;
    }
    now->next = NULL;
    head->next = now;
}

/** 手动冒泡*/
void sortList(ListNode *head) {
    int t = 10;
    while (t--) {
        int max = INT_MAX;
        ListNode *temp = head->next;
        while (temp->data < max && temp != NULL && temp->next != NULL) {
            if (temp->data > temp->next->data) {
                int t = temp->data;
                temp->data = temp->next->data;
                temp->next->data = t;
            }
            temp = temp->next;
        }
        max = temp->data;
        showList(head);
    }
}

void showList(ListNode *head) {
    head = head->next;
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

/** 递归之*/
void reserveShowList(ListNode *head) {
    if (head == NULL) {
        return ;
    }
    reserveShowList(head->next);
    printf("%d ", head->data);
}
